package cn.cxq.learning.string_matching;

/**
 * kmp算法
 */
public class KMPAlgorithmMatch {

    private String matchingStr; //匹配的串
    private String matchedStr; //被匹配的串
    private int[] next; //部分匹配值表

    public KMPAlgorithmMatch(String matchingStr, String matchedStr) {

        this.matchingStr = matchingStr;
        this.matchedStr = matchedStr;



        initNext();
    }

    /**
     * 初始化部分匹配值表
     */
    private void initNext() {

        this.next = new int[matchedStr.length()];

        this.next[0] = 0;

        for (int i = 1, j = 0; i < this.matchedStr.length(); i++) {

            while (j > 0 && this.matchedStr.charAt(i) != this.matchedStr.charAt(j)) {
                j = next[j - 1];
            }

            if (this.matchedStr.charAt(i) == this.matchedStr.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }

    /**
     * 展示部分匹配值表
     */
    public void showNext(){
        for (int i = 0; i < this.next.length; i++) {
            System.out.print(this.next[i] + " ");
        }
        System.out.println();
    }

    /**
     * 搜索
     * @return 找到被匹配字符串在匹配字符串中首个字母对应的下标
     */
    public int search() {
        for (int i = 0, j = 0; i < this.matchingStr.length(); i++) {

            if (j > 0 && this.matchedStr.charAt(j) != this.matchingStr.charAt(i)) {
                j = next[j - 1];
            }

            if (this.matchingStr.charAt(i) == this.matchedStr.charAt(j)) {
                j++;
            }
            if (j == this.matchedStr.length()) {
                System.out.println("找到了，首字母下标是" + (i - j + 1) + "~~~");
                return i - j + 1;
            }
        }
        System.out.println("未找到匹配的串~~~");
        return -1;
    }
}
